package com.hp.test.interview.tree;


class Count {
    int size;
}

/**
 * http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
 * A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present
 * in its left subtree and right subtree
 */
public class SumTree {

    public static void main(String args[]) {
        ConstructTreeFromInOrderPreOrder ctf = new ConstructTreeFromInOrderPreOrder();
        int inorder[] = {4, 10, 6, 46, 11, 13, 2};
        int preorder[] = {46, 10, 4, 6, 13, 11, 2};
        Node root = ctf.createTree(inorder, preorder);
        SumTree st = new SumTree();
        System.out.println(st.isSumTree(root));
    }

    public boolean isSumTree(Node root) {
        Count count = new Count();
        return isSumTree(root, count);
    }

    private boolean isSumTree(Node root, Count count) {
        if (root == null) {
            return true;
        }
        if (root.left == null && root.right == null) {
            count.size = root.data;
            return true;
        }
        Count leftCount = new Count();
        Count rightCount = new Count();
        boolean isLeft = isSumTree(root.left, leftCount);
        boolean isRight = isSumTree(root.right, rightCount);
        count.size = root.data + leftCount.size + rightCount.size;
        return isLeft && isRight && root.data == (leftCount.size + rightCount.size);
    }
}
